#if 1
#include <iostream>
#include <array>
#include <algorithm>

using namespace std;

static array<int8_t, 1000'0000> arr;

int main() {
    auto sum_square_digit = [](uint64_t a) {
        uint64_t s = 0;
        while (a) {
            uint64_t d = a % 10;
            s += d * d;
            a /= 10;
        }
        return s;
    };
    arr[1] = 1;
    arr[89] = 89;
    for (auto i = 1; i < arr.size(); ++i) {
        auto t = i;
        while (true) {
            if (arr[t] == 89) {
                arr[i] = 89;
                break;
            } else if (arr[t] == 1) {
                arr[i] = 1;
                break;
            } else {
                t = sum_square_digit(t);
            }
        }
    }
    cout << count(arr.begin(), arr.end(), 89) << endl; // 0.4s
}

#else 
#include <iostream>
#include <unordered_set>

using namespace std;

unordered_set<uint64_t> set1 {1};
unordered_set<uint64_t> set89 {89};

int main() {
    auto sum_square_digit = [](uint64_t a) {
        uint64_t s = 0;
        while (a) {
            uint64_t d = a % 10;
            s += d * d;
            a /= 10;
        }
        return s;
    };
    // for (auto i = 1; i < 50; ++i) {
    for (auto i = 1; i < 1000'0000ULL; ++i) {
        auto t = i;
        while (true) {
            if (set1.find(t) != set1.end()) {
                set1.insert(i);
                break;
            } else if (set89.find(t) != set89.end()) {
                set89.insert(i);
                break;
            } else {
                t = sum_square_digit(t);
            }
        }
    }
#if 0
    for (auto e : set1)
        cout << e << ' ';
    cout << endl;
    for (auto e : set89)
        cout << e << ' ';
    cout << endl;
#endif
    cout << set89.size() << endl; // 7s
}
#endif